package com.company.Sort;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}20:02
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {1,58,-1,5,6,-2};
        quicSort(arr);
    }

    public static void quicSort(int[] array){
        int len;
        if (array == null || (len = array.length) == 0 || len == 1){
            return;
        }
        sort(array,0,len-1);
    }

    public static void sort(int[] array, int left, int right){//没有中间值的快排？？？？
        if (left > right){
            return;
        }
        int base = array[left];
        int i = left,j = right;
        while (i != j){
            //先从右往左边找 找到比base小的数便记录
            while (array[j] >= base && i < j){
                j--;
            }

            //从左往右找 找到比base大的数便记录
            while (array[i] <= base && i <j){
                i++;
            }

            if (i < j){
                int t = array[i];
                array[i] = array[j];
                array[j] = t;
            }
        }
        array[left] = array[i];
        array[i] = base;//array[i]一定小于array[left]

        sort(array,left,i-1);//尝试将右边向前移动一位
        sort(array,i+1,right);//尝试将左边向前移动一位
        System.out.println(Arrays.toString(array));
    }

}
